package com.apkcore.bl;

/**
 * https://leetcode-cn.com/problems/stone-game/
 */
public class _877石子游戏 {

    public static void main(String[] args) {
//        int[] piles = {5, 3, 4, 5};
        int[] piles = {3, 2, 10, 4};
        System.out.println(new _877石子游戏().stoneGame(piles));
    }

    /**
     * 动态规则
     * 动态规划思想是希望连续的，也就是说上一个状态和下一个状态(自变量)之间有关系而且连续。
     *
     * dp[i][j]：表示先手玩家（亚历克斯）与后手玩家（李）在区间 [i, j][i,j] 之间互相拿，先手玩家比后手玩家多的最大石子个数。这是个差值，而且是个最大差值。
     *
     * 对于先手玩家，有两种拿法：
     *
     * 拿开头的 piles[i]piles[i]：先手玩家手里有了 piles[i]piles[i]，因为在区间 [i + 1, j][i+1,j] 中只能由后手玩家来选择，则 dp[i + 1][j]dp[i+1][j] 表示的是后手玩家在这个区间内，比先手玩家多的最大石子个数，反过来 -dp[i + 1][j]−dp[i+1][j] 表示在这个区间内，先手玩家比后手玩家多的最大石子个数；
     * 状态转移方程：dp[i][j] = piles[i] + (-dp[i + 1][j])
     *
     * 拿结尾的 piles[j]piles[j]：先手玩家手里有了 piles[j]piles[j]，因为在区间 [i, j - 1][i,j−1] 中只能由后手玩家来选择，则 dp[i][j - 1]dp[i][j−1] 表示的是后手玩家在这个区间内，比先手玩家多的最大石子个数，反过来 -dp[i][j - 1]−dp[i][j−1] 表示在这个区间内，先手玩家比后手玩家多的最大石子个数；
     * 状态转移方程：dp[i][j] = piles[j] + (-dp[i][j - 1])
     *
     * 在这两种情况中，选择先手玩家和后手玩家选择石子堆后，石子个数差更大的一种情况：dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])dp[i][j]=Math.max(piles[i]−dp[i+1][j],piles[j]−dp[i][j−1])
     *
     * 初始化：当只有一个数时 dp[i][i]dp[i][i]，此时先手玩家拿了必赢，所以 dp[i][i] = piles[i]dp[i][i]=piles[i]。
     *
     * 链接：https://leetcode-cn.com/problems/stone-game/solution/shi-zi-you-xi-dong-tai-gui-hua-qu-jian-d-5ra8/
     */
    public boolean stoneGame(int[] piles) {
        int[][] dp = new int[piles.length][piles.length];
        for (int i = 0; i < piles.length; i++) {
            dp[i][i] = piles[i];
        }
        for (int i = piles.length - 2; i >= 0; i--) {
            for (int j = i + 1; j < piles.length; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][piles.length - 1] > 0;
    }

    /**
     * 长度n，且n%2==0
     * 当先手选择第一个时，那么别人只能选择2或者最后n，偶数
     * 当先手选择最后一个，那么别人只能选择1或者n-1，奇数
     * 那么，先手完全可以先判断奇数和大还是偶数大，控制选择
     */
    public boolean stoneGame1(int[] piles) {
        return true;
    }
}
